//有向无环图的拓扑排序

#include <iostream>
#include "algraph.h"
#include "sqqueue.h"

using namespace std;

//拓扑排序算法 TopologicalSort(G)
//对图 G 进行拓扑排序，按拓扑有序的顺序输出顶点
template <typename V, typename E, int M>
void TopologicalSort(ALGraph<V,E,M> G)
{
    //计算每个顶点的入度 indegree[]
    int indegree[M] = {0}; //全部初始化为零
    for(int v=0; v<G.vexnum; v++){
        for(auto p=G.vexs[v].firstarc; p; p=p->nextarc){
            int w = p->adjvex;
            indegree[w]++;
        }
    }


    //所有入度为零的顶点，入队列 Q
    SqQueue<int, M> Q;
    InitQueue(Q);
    for(int v=0; v<G.vexnum; v++)
        if(indegree[v] == 0)
            EnQueue(Q, v);

    //逐个输出入度为零的顶点并删除之，并将新的入度为零的顶点入队列
    int count = 0;
    while(!QueueEmpty(Q)){
        //取一个入度为零的顶点 v
        int v;
        DeQueue(Q, v);
        //取一个入度为零的顶点 v
        std::cout << G.vexs[v].data;
        count++;
        //顶点 v 所有邻接点入度减 1
        for(auto p=G.vexs[v].firstarc; p; p=p->nextarc){
            int w = p->adjvex;
            indegree[w]--;
            //如果 w 入度为零则入队列
            if(indegree[w] == 0)
                EnQueue(Q, w);
        }
    }

    //结论：如果图中存在回路，提示信息/抛出异常
    if(count < G.vexnum)
        throw "Graph has a cycle";
}

//主函数测试拓扑排序
int main()
{
    //建立有向无环图
    //G = ({A,B,C,D,E}, {AB,AC,BD,BE,CD,CE,DE})
    ALGraph<char, int> G;
    //初始化
    InitGraph(G);
    //添加顶点
    auto a = AddVertex(G, 'A');
    auto b = AddVertex(G, 'B');
    auto c = AddVertex(G, 'C');
    auto d = AddVertex(G, 'D');
    auto e = AddVertex(G, 'E');
    //添加边
    AddArc(G, a, b, 1);
    AddArc(G, a, c, 1);
    AddArc(G, b, d, 1);
    AddArc(G, b, e, 1);
    AddArc(G, c, d, 1);
    AddArc(G, c, e, 1);
    AddArc(G, d, e, 1);

    //拓扑排序
    cout << "TopologicalSort: ";
    TopologicalSort(G);

    return 0;
}